UVa/11487 - Gathering Food/gathering.cpp

   1 #include <iostream>
   2 #include <queue>
   3 using namespace std;
   4
   5 bool v[11][11][27];
   6 int dp[11*11*27][11][11][27];
   7 char g[11][11];
   8
   9 struct state{
  10     int i, j, w;
  11     char last;
  12     state(){} state(int I, int J, char L, int W) : i(I), j(J), last(L), w(W) {}
  13 };
  14
  15 int n;
  16 char final;
  17 int di[] = {-1, +1, +0, +0};
  18 int dj[] = {+0, +0, +1, -1};
  19
  20 #define inside(i, j) (0 <= i && i < n && 0 <= j && j < n)
  21 #define D(x) cout << #x " es " << x << endl
  22 #define unchar(c) ((c)-'A')
  23
  24 const int mod = 20437;
  25
  26 void bfs(int si, int sj){
  27      memset(v, 0, sizeof v);
  28      memset(dp, 0, sizeof dp);
  29      dp[0][si][sj][0] = 1;
  30
  31      queue<state> q;
  32      q.push(state(si, sj, 'A', 0));
  33      while (q.size()){
  34          int i = q.front().i, j = q.front().j, w = q.front().w;
  35          char last = q.front().last;
  36          //printf("popped (%d, %d, %c, %d)\n", i, j, last, w);
  37          q.pop();
  38          if (v[i][j][unchar(last)]) continue;
  39          v[i][j][unchar(last)] = true;
  40
  41          if (g[i][j] == final){
  42             //Llegue
  43             cout << w << " " << (dp[w][i][j][unchar(last)] % mod) << endl;
  44             return;
  45          }
  46          int new_paths = dp[w][i][j][unchar(last)];
  47          if (g[i][j] == last) g[i][j] = '.', last++;
  48          //D(new_paths);
  49          for (int k=0; k<4; ++k){
  50              int ni = i + di[k], nj = j + dj[k];
  51              if (inside(ni, nj) && !v[ni][nj][unchar(last)] && (g[ni][nj] == '.' || g[ni][nj] == last)){
  52                 dp[w+1][ni][nj][unchar(last)] = ((dp[w+1][ni][nj][unchar(last)])%mod + (new_paths)%mod)%mod;
  53                 q.push(state(ni, nj, last, w+1));
  54              }
  55          }
  56      }
  57      cout << "Impossible" << endl;
  58 }
  59
  60 int main(){
  61     int C=1;
  62     while (cin >> n && n){
  63        int si, sj;
  64        final = 'A';
  65        for (int i=0; i<n; ++i){
  66            for (int j=0; j<n; ++j){
  67                cin >> g[i][j];
  68                if (g[i][j] == 'A') si = i, sj = j;
  69                if (g[i][j] > final) final = g[i][j];
  70            }
  71        }
  72        cout << "Case " << C++ << ": ";
  73        bfs(si, sj);
  74     }
  75     return 0;
  76 }